package 剑指Offer.简单;

/**
 * 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
 * <p>
 * 示例 1:
 * <p>
 * 输入: n = 1
 * 输出: [1,2,3,4,5,6,7,8,9]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2022/8/22 13:33
 */
public class _17打印从1到最大的n位数 {

    /**
     * 普通遍历
     */
    public int[] printNumbers(int n) {
        int len = (int) Math.pow(10, n) - 1;
        int[] nums = new int[len];
        int i = 0;
        while (i < len) {
            nums[i] = ++i;
        }
        return nums;
    }

    /**
     * 全排列版本 针对大数情况
     */
    private final char[] loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    private int most;
    private char[] chars;
    private StringBuilder sb = new StringBuilder();
    public String printNumbers_v2(int n) {
        most = n;
        chars = new char[n];
        dfs(0);
        return sb.toString();
    }
    
    private void dfs(int n) {
        if (n == most) {
            sb.append(String.valueOf(chars)).append(",");
            return;
        }
        for (char c : loop) {
            // 固定第n位数
            chars[n] = c;
            dfs(n + 1);
        }
    }


    public static void main(String[] args) {
        _17打印从1到最大的n位数 a = new _17打印从1到最大的n位数();
        String s = a.printNumbers_v2(2);
        System.out.println(s);
    }
}
